home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / progtool / prolog / dokument / anhang.doc next >
Encoding:
Text File  |  1994-09-22  |  16.7 KB  |  378 lines
  1.  
  2.  
  3.                               Anhang
  4.  
  5.           zur Dokumentation von TOY Prolog ST, Version 3
  6.  
  7.      Inhalt
  8.  
  9. A.1  Aufbau des Interpreters
  10. A.2  Syntax des inneren Interpreters
  11. A.3  Die Systemdatei
  12. A.4  Die Implementierung der Benutzerschnittstelle
  13. A.5  Erweiterungen  in der vorliegenden Version von TOY Prolog  ST 
  14.      in Bezug auf die Dokumentation.
  15.  
  16.  
  17.      A.1 Der Aufbau des Interpreters
  18.  
  19. TOY  Prolog besteht aus zwei Teilen,  dem inneren und dem  äußeren 
  20. Interpreter.  Der  innere Interpreter ist in C und 68000-Assembler 
  21. geschrieben,  der äußere bereits in Prolog selbst.  Der Vorteil an 
  22. einer   derartigen  Implementierung  ist,   daß  viele  Teile  des 
  23. Interpreters in Prolog erheblich leichter zu formulieren sind  als 
  24. in anderen Programmiersprachen.
  25.  
  26. Ein Beispiel dafür ist das Prädikat 'repeat'.  In Prolog ist es wie 
  27. folgt definiert :
  28.  
  29.      repeat.
  30.      repeat :- repeat.
  31.  
  32. Eine  Implementierung  von  'repeat' in  C  würde  erfordern,  die 
  33. Datenstrukturen,   die  der  innere  Interpreter   verwendet,   zu 
  34. erweitern; der entstehende Mehraufwand wäre beträchtlich.
  35.  
  36. Die  verwendete Technik hat natürlich auch Nachteile.  Der  größte 
  37. davon  ist  zweifelsohne der der geringeren  Geschwindigkeit.  Der 
  38. gesamte   Parser  von  TOY  Prolog  ist  im  äußeren   Interpreter 
  39. implementiert,  und aufgrund der komplexen Syntax (TOY Prolog soll 
  40. weitgehend  mit  Prolog-10 kompatibel sein) ist  der  Parser  sehr 
  41. aufwendig.  Man  merkt das besonders schmerzlich beim Einlesen von 
  42. Dateien mit 'consult' etc.
  43.  
  44. Die geringe Geschwindigkeit beim Einlesen von Programmen kann  man 
  45. auf eine einfache Weise umgehen. Sobald man ein korrektes Programm 
  46. vorliegen hat,  kann man es in die Syntax des inneren Interpreters 
  47. übersetzen.  Die Geschwindigkeit,  mit der derartige Zwischencodes 
  48. eingelesen  werden,  übertrifft bei weitem die Lesegeschwindigkeit 
  49. des äußeren Interpreters.
  50.  
  51.  
  52. Der   äußere  Interpreter  besteht  im  wesentlichen   aus   einer 
  53. Programmschleife (loop / 0), die Terme mit 'read' einliest und sie 
  54. auswertet. Diese Schleife kann auch aus Benutzerprogrammen mit
  55.  
  56.      tag(loop)
  57.  
  58. aufgerufen werden; sie wird durch das Prädikat 'stop' abgebrochen. 
  59. Diese Möglichkeit wird z.B. im Editor verwendet.
  60.  
  61. Die  Art  und Weise der Implementierung verlangt,  daß der  äußere 
  62. Interpreter  nach dem Programmstart eingelesen wird.  Deshalb gibt 
  63. es  in  TOY  Prolog eine  Systemdatei  namens  'SYSFILE.TOY'.  Sie 
  64. enthält  außer  dem  Zwischencode des  äußeren  Interpreters  noch 
  65. andere  wichtige Daten,  insbesondere die Namen und  Stelligkeiten 
  66. der  Systemfunktionen  und  die  Definitionen  der  vordefinierten 
  67. Prädikate.  Der  Aufbau  der  Systemdatei wird  in  Abschnitt  A.3 
  68. erläutert.
  69.  
  70.  
  71.      A.2 Die Syntax des inneren Interpreters
  72.  
  73. Die Syntaxbeschreibung erfolgt analog zur Beschreibung der  vollen 
  74. Syntax in Abschnitt II.
  75.  
  76. Klausel             ::=  Regel | Ziel
  77. Regel               ::=  F_Term : Aufrufliste
  78. Ziel                ::=  : Aufrufliste #
  79. Aufrufliste         ::=  { Aufruf . } []
  80. Aufruf              ::=  F_Term
  81.  
  82. F_Term              ::=  Funktor | Funktor ( Argumente )
  83. Funktor             ::=  Name | Q_Name | [] | !
  84. Argumente           ::=  Term { , Term }
  85. Term                ::=  (  Term  ) | Variable | Zahl |  F_Term  | 
  86.                          Term . Term
  87. Variable            ::=  Anonyme_Variable | Numerierte_Variable
  88. Anonyme_Variable    ::=  _
  89. Numerierte_Variable ::=  : Zahl
  90.  
  91. Zahl                ::=  Vorzeichen Ziffer { Ziffer }
  92. Name                ::=  Kleinbuchstabe { Alphanumerisch }
  93. Q_Name              ::=  ' Q_Zeichen { Q_Zeichen } '
  94. Q_Zeichen           ::=  '' | Nicht_'
  95. *** Nicht_' ist jedes Zeichen außer '
  96. Alphanumerisch      ::=  Kleinbuchstabe | Großbuchstabe |
  97.                          Ziffer | _
  98. Vorzeichen          ::=  + | | -
  99. *** Das Vorzeichen kann auch fehlen.
  100. *** Kleinbuchstabe, Großbuchstabe, Ziffer siehe Abschnitt II.
  101.  
  102.  
  103. Erläuterungen
  104.  
  105. (1)  Der innere Interpreter liest nur Regeln und Ziele ein,  wobei 
  106.      ein Ziel syntaktisch eine Regel ohne Kopf ist.  Fakten müssen 
  107.      als  Regeln repräsentiert werden,  bei denen die  Aufrufliste 
  108.      gleich  [] ist.  Ein Ziel wird durch das Zeichen '#' beendet, 
  109.      das  dem Interpreter mitteilt,  daß er mit der Auswertung des 
  110.      Ziels (d.h.  mit dem Versuch,  das Ziel zu erfüllen) beginnen 
  111.      soll.  Es  wird keine Meldung über Gelingen oder Fehlschlagen 
  112.      des Ziels ausgegeben.
  113.  
  114. (2)  Soll  der innere Interpreter vom Datenstrom 'user' lesen,  so 
  115.      verhält er sich, als habe er das Ziel
  116.  
  117.           : ear . [] #
  118.  
  119.      eingelesen.   Dieses   Ziel   ist  der  Aufruf  des   äußeren 
  120.      Interpreters  und muß daher als Prädikat vorhanden sein;  für 
  121.      den  Fall,   daß  ein  anderes  Prädikat  als  'ear'  in  der 
  122.      Systemdatei  (siehe  Abschnitt A.3) eingetragen  wurde,  gilt 
  123.      sinngemäß dasselbe.
  124.  
  125. (3)  Anonyme  Variablen,  die  der  innere  Interpreter  einliest, 
  126.      verhalten sich anders als anonyme Variablen,  die vom äußeren 
  127.      Interpreter eingelesen werden. Der innere Interpreter erzeugt 
  128.      'echte' anonyme Variablen,  die nicht mit Werten instantiiert 
  129.      werden  können.  Der äußere Interpreter erzeugt statt  dessen 
  130.      einmalige Instanzen von 'normalen' Variablen. Der Unterschied 
  131.      ist  normalerweise bedeutungslos;  man sollte sich aber nicht 
  132.      darauf  verlassen,   daß  z.B.   'numbervars'  wirklich  alle 
  133.      Variablen instantiiert.
  134.  
  135. (4)  Beim Einlesen von 'numerierten' Variablen erzeugt der  innere 
  136.      Interpreter eine Tabelle,  anhand derer er erkennt,  wieviele 
  137.      verschiedene Variablen ein Term enthält. Der Term
  138.  
  139.           f( :1, :100)
  140.  
  141.      erfordert also nicht 100,  sondern nur 2 Variablen. Die einer 
  142.      Variablen  bei der Eingabe zugeordnete Nummer hat nichts  mit 
  143.      der  von 'display' oder 'write' ausgegebenen  Variablennummer 
  144.      zu  tun;  'display'  benutzt die interne  Repräsentation  von 
  145.      Variablen, 'write' deren Reihenfolge im Term.
  146.  
  147.  
  148.      A.3 Die Systemdatei
  149.  
  150. Die Systemdatei 'SYSFILE.TOY' besteht aus drei Teilen :
  151.  
  152. -    den  Namen  und Stelligkeiten bestimmter Funktoren,  die  vom 
  153.      inneren  Interpreter für besondere Aufgaben benötigt  werden. 
  154.      Es  sind  ';' und ',' (benötigt für die  Implementierung  des 
  155.      'cut'),  'tag'  und  'call',  '[]' und '.',  'error' (für die 
  156.      Behandlung von Aufruffehlern), 'user' (für die Ein-/Ausgabe), 
  157.      die  Operatortypen  und  'ear' (das  Ziel,  das  vom  inneren 
  158.      Interpreter aufgerufen wird).
  159.      Die  Beschreibungen dieser Funktoren sollten nicht  verändert 
  160.      werden;  ausgenommen  davon  ist 'ear',  das geändert  werden 
  161.      kann,  um  ein  anderes  Ziel  vom  inneren  Interpreter  aus 
  162.      aufrufen zu lassen.
  163.  
  164. -    den  Namen und Stelligkeiten der Systemfunktionen.  Die Namen 
  165.      der  Systemfunktionen können beliebig geändert  werden,  aber 
  166.      die  Stelligkeiten  müssen erhalten bleiben.  Wird  der  Name 
  167.      einer  Systemfunktion geändert,  so muß die Änderung in allen 
  168.      Programmen, insbesondere im äußeren Interpreter, durchgeführt 
  169.      werden;  andernfalls  sind  Programme,  die  die  betreffende 
  170.      Funktion benutzen, nicht mehr lauffähig !
  171.  
  172. -    der  Systembibliothek.  Diese  enthält  (in  der  Syntax  des 
  173.      inneren  Interpreters)  die Definitionen  der  vordefinierten 
  174.      Prädikate und den Zwischencode des äußeren Interpreters. Auch 
  175.      hier  gilt für Namensänderungen das oben gesagte;  Änderungen 
  176.      der  Definitionen haben nicht so weitreichende  Folgen,  aber 
  177.      sie    können   durchaus   dazu   führen,    daß    Programme 
  178.      (einschließlich  der  Hilfsprogramme)  nicht  mehr  lauffähig 
  179.      sind.  Zu  Veränderungen an der Benutzerschnittstelle wird im 
  180.      Abschnitt A.4 noch näheres gesagt.
  181.  
  182. Die  Beschreibungen  der  Spezialfunktoren  und   Systemfunktionen 
  183. werden zur Initialisierung des inneren Interpreters verwendet; sie 
  184. werden eingelesen,  nachdem AES,  VDI und die Speicherbereiche des 
  185. Interpreters initialisiert wurden.
  186. Die  Systembibliothek  wird direkt nach  der  Initialisierung  des 
  187. inneren Interpreters eingelesen; am Dateiende steht ein 'seen', so 
  188. daß nach dem Einlesen der äußere Interpreter gestartet wird.
  189.  
  190.  
  191.      A.4 Die Implementierung der Benutzerschnittstelle
  192.  
  193. Die  Syntax des inneren Interpreters ist zwar sehr einfach,  dafür 
  194. sind  Programme  in  dieser  Form  nur  schwer  verständlich;  ein 
  195. Programm von der Größenordnung des äußeren Interpreters kann daher 
  196. nicht direkt im Zwischencode entwickelt werden.
  197. Aus   diesem  Grund  wurde  die  Benutzerschnittstelle  in   einer 
  198. Untermenge  der  zu implementierenden Sprache  geschrieben.  Diese 
  199. "Halbsprache" ist in folgenden Punkten gegenüber der vollständigen 
  200. Syntax eingeschränkt:
  201.  
  202. -    Operatornotation und die Verwendung von grammatischen  Regeln 
  203.      ist nicht erlaubt.
  204. -    Die  Listennotation ist leicht eingeschränkt :  In einem Term 
  205.      der Form
  206.  
  207.           [ A, B, C ... | X ]
  208.  
  209.      muß X eine Variable sein.
  210. -    Das  Komma  in  einer Regel und das Symbol  ':-'  werden  als 
  211.      Trennzeichen  (nicht als Operatoren) behandelt.  ';' darf  in 
  212.      einer  Regel  nicht als Trennzeichen,  wohl aber als  Funktor 
  213.      verwendet werden.
  214.  
  215. Das Hilfsprogramm 'BOOTER.TOY' kann diese Notation praktisch 1 : 1 
  216. in den Zwischencode übersetzen.
  217.  
  218. Der Quellcode der Benutzerschnittstelle befindet sich in der Datei 
  219. 'MONITOR.PRO';   nach   der   Übersetzung  sollte  man   aus   dem 
  220. entstandenen  Zwischencode  alle Kommentare  entfernen,  da  diese 
  221. ziemlich viel Platz verbrauchen. Dabei ist zu beachten, daß manche 
  222. Prädikate,   die   Kommentare  erkennen  oder  erzeugen  (in   der 
  223. vorliegenden   Version   sind   es   'skip',   'absorbtoken'   und 
  224. 'nextline'), das Zeichen '%' benutzen; man darf also nicht einfach 
  225. alle Zeilen löschen, in denen '%' vorkommt.
  226.  
  227. Über  die  Verfahren,  die beim Entwurf des  äußeren  Interpreters 
  228. angewandt wurden,  und über dessen Aufbau, kann hier nichts gesagt 
  229. werden;  eine ausführliche Beschreibung findet sich in "Prolog for 
  230. Programmers".
  231.  
  232.  
  233.      A.5 Unterschiede zur Dokumentation
  234.  
  235. In  der vorliegenden Version 3.3 gibt es folgende Unterschiede  zu 
  236. dieser Dokumentation:
  237.  
  238. -    Die  Betätigung  der  Tasten 'Control' 'C'  führt  in  vielen 
  239.      Fällen zum sofortigen Abbruch des äußeren  Interpreters.  Das 
  240.      Programm verhält sich so, als ob nach einer Unterbrechung mit 
  241.      'Shift'  'Alternate'  'Help' die Option A  (Abbruch)  gewählt 
  242.      wurde.
  243.      Der  innere Interpreter wird nicht abgebrochen;  wird  gerade 
  244.      keine Datei eingelesen, so wird der äußere Interpreter wieder 
  245.      gestartet.
  246.  
  247. -    Falls  bei  einer Diskettenoperation  ein  kritischer  Fehler 
  248.      (Wechsel  der  Diskette,  falsche Diskette im Laufwerk  etc.) 
  249.      auftritt, erfolgt die Meldung:
  250.  
  251.      There was a critical error. (A)bort, (R)etry or (I)gnore ?
  252.  
  253.      Die   Eingabe   von  'A'  führt  zum   Abbruch   (mit   einer 
  254.      Fehlermeldung);  'R'  veranlaßt einen neuen Versuch,  und bei 
  255.      'I' wird der Fehler ignoriert (Vorsicht !).
  256.  
  257. -    Die  Anzeige  der Teilziele  im  Testmodus  ("CALL",  "REDO", 
  258.      "EXIT",  "FAIL")  funktioniert (noch) nicht  richtig.  "FAIL" 
  259.      wird  bei  jedem  Mißerfolg,   auch  vor  einem  'backtrack', 
  260.      angezeigt,   nicht  nur  (wie  es  richtig  wäre)  nach   dem 
  261.      endgültigen Fehlschlag des Teilzieles. Im Gegensatz dazu wird 
  262.      "EXIT"   nicht   bei  allen  erfolgreich   erfüllten   Zielen 
  263.      angezeigt.
  264.      Es  ist zweifelhaft,  ob diese Mißstände noch behoben  werden 
  265.      (können   ?).   Der  "FAIL"-Fehler  ist   beim   Programmtest 
  266.      hinderlich und wird wahrscheinlich noch ausgemerzt,  aber der 
  267.      "EXIT"-Fehler   ist  teilweise  durch  die   optimierte   (!) 
  268.      Ausführung  von  rekursiven  Prädikaten bedingt  und  kann  - 
  269.      zumindest in dieser Situation - nicht verhindert werden.
  270.      (TOY  Prolog führt eine 'tail recursion  optimisation'  (TRO) 
  271.      durch,  d.h.,  daß  die 'activation records'  von  Prädikaten 
  272.      zerstört werden können,  falls dadurch Speicher gespart wird. 
  273.      Der  Name  kommt von rekursiven  Prädikaten,  bei  denen  der 
  274.      rekursive Aufruf der letzte in seiner Klausel ist; allerdings 
  275.      erstreckt sich die TRO auch auf andere Situationen,  wie z.B. 
  276.      den 'cut')
  277.  
  278.  
  279. -    Es  wurden drei weitere Systemfunktionen  implementiert,  die 
  280.      auf die Dateiverzeichnisse des Betriebssystems zugreifen :
  281.  
  282. disk_dir (VAR)
  283.      instantiiert    PAR_1   mit   dem   Namen    des    aktuellen 
  284.      Dateiverzeichnisses,  d.h.  mit der Laufwerksbezeichnung  und 
  285.      dem Pfadnamen.
  286.  
  287. disk_dir (NAME)
  288.      macht   das  durch  PAR_1  angegebene  Dateiverzeichnis   zum 
  289.      aktuellen  Dateiverzeichnis.  Die  Laufwerksbezeichnung  kann 
  290.      fehlen;  in  diesem Fall wird das aktuelle Laufwerk  benutzt. 
  291.      Ist PAR_1 fehlerhaft, so wird ein Systemaufruffehler erzeugt.
  292.  
  293. disk_search (NAME, INTEGER, TERM, TERM)
  294.      PAR_1  und PAR_2 sind Parameter für den  Betriebssystemaufruf 
  295.      F_SFIRST  :  Es  wird  nach der  ersten  Datei  im  aktuellen 
  296.      Dateiverzeichnis (oder in einem Verzeichnis,  das durch einen 
  297.      in  PAR_1 vorhandenen Pfadnamen bestimmt wird)  gesucht,  die 
  298.      dem Suchmuster in PAR_1 entspricht,  und deren Attribute  dem 
  299.      Suchattribut PAR_2 entsprechen.  Das Suchmuster wird wie  ein 
  300.      Dateiname angegeben;  allerdings können hier die 'wild cards' 
  301.      *  und  ?  benutzt werden.  Im Pfadnamen dürfen  keine  'wild 
  302.      cards' stehen.
  303.      Die  Suchattribute  werden in PAR_2  bitweise  angegeben;  im 
  304.      einzelnen bedeutet
  305.  
  306.           0    Normaler Dateizugriff möglich
  307.           1    Datei ist schreibgeschützt
  308.           2    Datei ist 'versteckt'
  309.           4    Datei ist 'Systemdatei' (ebenfalls versteckt)
  310.           8    keine Datei, sondern der Name der Diskette
  311.           16   keine Datei, sondern Dateiverzeichnis
  312.           32   Datei wurde beschrieben und geschlossen (???)
  313.  
  314.      Falls keine entsprechende Datei gefunden wurde,  schlägt  der 
  315.      Aufruf fehl; ansonsten wird versucht, PAR_3 mit dem Namen und 
  316.      PAR_4 mit den Attributen der gefundenen Datei zu unifizieren.
  317.  
  318. disk_search (TERM, TERM)
  319.      sucht  nach der nächsten Datei,  deren Name und Attribute  zu 
  320.      den   im   letzten  Aufruf  von   disk_search/4   angegebenen 
  321.      Suchmustern passen,  und versucht,  PAR_3 mit dem  Dateinamen 
  322.      und  PAR_4  mit den zugehörigen  Attributen  zu  unifizieren. 
  323.      Falls  keine passende Datei mehr gefunden wird,  schlägt  der 
  324.      Aufruf fehl.
  325.  
  326.  
  327. -    Die Eingabe von der Tastatur (Datenströme 'user' und 'keybd') 
  328.      wurde verändert.  Insbesondere werden die Funktionstasten (F1 
  329.      bis F10 und der Cursorblock) jetzt ausgenutzt.
  330.      Es   besteht  die  Möglichkeit,   die   Funktionstasten   mit 
  331.      Zeichenketten   zu   belegen,    die   beim   Betätigen   der 
  332.      entsprechenden Tasten so interpretiert werden, als ob sie von 
  333.      der Tastatur aus eingegeben wurden.
  334.      Dazu dient die neue Systemfunktion
  335.  
  336. set_fstring (INTEGER, NAME).
  337.      PAR_1 muß eine Integerzahl aus dem Bereich von 0 bis 27 sein, 
  338.      die  die  gewünschte  Funktionstaste  auswählt  (s.u.).   Die 
  339.      ausgewählte   Funktionstaste  wird  mit  einer   Zeichenkette 
  340.      belegt,  die durch den Namen von PAR_2 gegeben ist (PAR_2 muß 
  341.      ein Funktor ohne Argumente sein).
  342.  
  343.      Die Funktionstasten sind wie folgt gekennzeichnet:
  344.  
  345.           0  F1          10  Shift/F1        20  Clr/Home
  346.           1  F2          11  Shift/F2        21  Cursor hoch
  347.           2  F3          12  Shift/F3        22  Cursor links
  348.           3  F4          13  Shift/F4        23  Cursor rechts
  349.           4  F5          14  Shift/F5        24  Cursor runter
  350.           5  F6          15  Shift/F6        25  Insert
  351.           6  F7          16  Shift/F7        26  Undo
  352.           7  F8          17  Shift/F8        27  Help
  353.           8  F9          18  Shift/F9
  354.           9  F10         19  Shift/F10
  355.  
  356.      Für die Zeichenkette gilt noch folgende Besonderheit :
  357.       Steht in der Zeichenkette ein '\',  so wird das nachfolgende 
  358.      Zeichen  so  interpretiert,  als ob die  entsprechende  Taste 
  359.      zusammen mit 'Control' gedrückt worden wäre. 
  360.      Ausnahme :  Ist das folgende Zeichen wieder ein '\',  so gilt 
  361.      es (wie üblich) als ein einzelnes '\'.
  362.  
  363.      Beispiele : \G - 'Bell', \H - 'Backspace',  \M - 'Return'.
  364.  
  365.  
  366. Geplante Änderungen :
  367.  
  368. -    Fehler im Testmodus, siehe oben.
  369.  
  370. -    Einbindung  von Programmen aus anderen Sprachen  (C,  Pascal, 
  371.      Assembler).
  372.  
  373.      (Falls ich jemals dazu komme,  mir dafür einen Grund und eine 
  374.      Vorgehensweise zu überlegen ...)
  375.  
  376.      Ende des Anhangs zur Dokumentation von TOY Prolog ST, Version 3
  377.  
  378.